package com.lft.ten_commonly_used_algorithms08.dijkstra;

import java.util.Arrays;

/**
 * 迪杰斯特拉算法
 */
public class DijkstraAlgorithmDemo {
	public static void main(String[] args) {
		char[] vertexes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		final int N = Integer.MAX_VALUE;
		int[][] matrix = {
				{N, 5, 7, N, N, N, 2},
				{5, N, N, 9, N, N, 3},
				{7, N, N, N, 8, N, N},
				{N, 9, N, N, N, 4, N},
				{N, N, 8, N, N, 5, 4},
				{N, N, N, 4, 5, N, 6},
				{2, 3, N, N, 4, 6, N}};
		Graph graph = new Graph(vertexes, matrix);
		graph.displayGraph();
		System.out.println();
		for (int i = 0; i < vertexes.length; i++) {
			System.out.println("顶点为：" + vertexes[i]);
			graph.dijkstra(i);
			graph.show();
			System.out.println();
			System.out.println("==============");
		}
	}
}

class VisitedVertex {
	// 记录各个顶点是否访问过 true 表示访问过。false 表示未访问过。
	boolean[] visited;
	// 每个下标对应的值为前一个顶点下标。会动态更新。
	int[] pre_vertex;
	// 记录出发顶点到其他所有顶点的距离，比如 G 为出发顶点，就会记录 G 到其余顶点的距离。会动态更新，求的最短距离就会存放到 dis 中。
	int[] dis;
	
	/**
	 * @param numOfVertexes 顶点个数
	 * @param vertexIndex   出发顶点索引
	 */
	public VisitedVertex(int numOfVertexes, int vertexIndex) {
		this.visited = new boolean[numOfVertexes];
		this.pre_vertex = new int[numOfVertexes];
		this.dis = new int[numOfVertexes];
		Arrays.fill(this.dis, Integer.MAX_VALUE);
		// 设置出发顶点的访问距离为0。
		this.dis[vertexIndex] = 0;
		this.visited[vertexIndex] = true;
	}
	
	/**
	 * 更新出发顶点到 vertexIndex 顶点的距离。
	 * @param vertexIndex 顶点索引
	 * @param length      距离
	 */
	public void updateDis(int vertexIndex, int length) {
		this.dis[vertexIndex] = length;
	}
	
	/**
	 * 更新 preVertexIndex 顶点的前驱为 newVertexIndex 顶点。
	 * @param preVertexIndex 前驱顶点索引
	 * @param newVertexIndex 新前驱顶点索引
	 */
	public void updatePreVertex(int preVertexIndex, int newVertexIndex) {
		this.pre_vertex[preVertexIndex] = newVertexIndex;
	}
	
	/**
	 * 返回出发顶点到目标顶点的最短路径距离。
	 * @param targetVertexIndex 目标顶点索引
	 */
	public int getDis(int targetVertexIndex) {
		return dis[targetVertexIndex];
	}
	
	/**
	 * 继续选择并返回新的访问顶点。比如这里的 G 顶点完后，就是 A B E F 顶点从 A 开始再依次访问。
	 * @return
	 */
	public int updateArray() {
		int min = Integer.MAX_VALUE;
		int index = 0;
		for (int i = 0; i < visited.length; i++) {
			if (!visited[i] && dis[i] < min) {
				min = dis[i];
				index = i;
			}
		}
		// 将 index 顶点更新为已经访问过
		visited[index] = true;
		return index;
	}
	
	/**
	 * 显示最后的结果
	 * 即将三个数组的情况输出。
	 */
	public void show() {
		System.out.println("顶点访问情况：");
		for (int i = 0; i < this.visited.length; i++) {
			System.out.print(this.visited[i] + "\t");
		}
		System.out.println();
		System.out.println("前驱顶点情况：");
		for (int i = 0; i < this.pre_vertex.length; i++) {
			System.out.printf("%d\t", this.pre_vertex[i]);
		}
		System.out.println();
		System.out.println("最小距离情况：");
		for (int i = 0; i < this.dis.length; i++) {
			System.out.printf("%d\t", this.dis[i]);
		}
	}
}

/**
 * 图类
 */
class Graph {
	/**
	 * 顶点数组
	 */
	private char[] vertex;
	
	/**
	 * 顶点数量
	 */
	private int numOfVertexes;
	/**
	 * 邻接矩阵
	 */
	private int[][] matrix;
	
	/**
	 * 边的数量
	 */
	private int numOfEdges;
	
	/**
	 * 已经访问的顶点的集合。
	 */
	private VisitedVertex visitedVertex;
	
	public Graph(char[] vertex, int[][] matrix) {
		// 初始化顶点数量
		this.numOfVertexes = vertex.length;
		// 初始化顶点数组
		this.vertex = new char[vertex.length];
		for (int i = 0; i < vertex.length; i++) {
			this.vertex[i] = vertex[i];
		}
		// 初始化邻接矩阵数组
		this.matrix = new int[this.numOfVertexes][this.numOfVertexes];
		for (int i = 0; i < numOfVertexes; i++) {
			for (int j = 0; j < numOfVertexes; j++) {
				this.matrix[i][j] = matrix[i][j];
				// 初始化边数。
				if (this.matrix[i][j] != 0 && this.matrix[i][j] != Integer.MAX_VALUE) {
					this.numOfEdges++;
				}
			}
		}
	}
	
	/**
	 * 迪杰斯特拉算法方法
	 * @param vertexIndex 出发顶点索引
	 */
	public void dijkstra(int vertexIndex) {
		this.visitedVertex = new VisitedVertex(vertex.length, vertexIndex);
		// 更新 vertexIndex 起始顶点到其余顶点的距离。
		update(vertexIndex);
		for (int i = 1; i < numOfVertexes; i++) {
			// 选择并返回新的访问顶点。
			vertexIndex = this.visitedVertex.updateArray();
			// 更新 vertexIndex 顶点到其余顶点的距离和前驱顶点。
			update(vertexIndex);
		}
	}
	
	/**
	 * 更新 vertexIndex 顶点到其余顶点的距离和其他顶点的前驱顶点。
	 * @param vertexIndex 顶点索引
	 */
	private void update(int vertexIndex) {
		int len = 0;
		// 遍历邻接矩阵。
		for (int j = 0; j < matrix[vertexIndex].length; j++) {
			// 出发顶点到 vertexIndex 顶点的距离 + vertexIndex 顶点到 j 顶点的和。
			len = this.visitedVertex.getDis(vertexIndex) + matrix[vertexIndex][j];
			// 如果 j 顶点没有被访问过，并且 顶点到 j 的距离 大于 顶点到 vertexIndex 顶点的距离 + vertexIndex 顶点到 j 顶点的距离
			if (!this.visitedVertex.visited[j] && matrix[vertexIndex][j] != Integer.MAX_VALUE && this.visitedVertex.getDis(j) > len) {
				// 更新 j 顶点的前驱节点为 vertexIndex
				this.visitedVertex.updatePreVertex(j, vertexIndex);
				// 更新 出发顶点到 j 顶点的距离为 len
				this.visitedVertex.updateDis(j, len);
				// // 设置 j 顶点为已访问。
				// this.visitedVertex.visited[j] = true;
			}
		}
	}
	
	/**
	 * 打印邻接矩阵
	 */
	public void displayGraph() {
		for (int[] link : matrix) {
			System.out.println(Arrays.toString(link));
		}
	}
	
	/**
	 * 显示
	 */
	public void show() {
		this.visitedVertex.show();
	}
}